/*
 * @lc app=leetcode.cn id=427 lang=typescript
 *
 * [427] 建立四叉树
 */

// @lc code=start
/**
 * Definition for node.
 * class Node {
 *     val: boolean
 *     isLeaf: boolean
 *     topLeft: Node | null
 *     topRight: Node | null
 *     bottomLeft: Node | null
 *     bottomRight: Node | null
 *     constructor(val?: boolean, isLeaf?: boolean, topLeft?: Node, topRight?: Node, bottomLeft?: Node, bottomRight?: Node) {
 *         this.val = (val===undefined ? false : val)
 *         this.isLeaf = (isLeaf===undefined ? false : isLeaf)
 *         this.topLeft = (topLeft===undefined ? null : topLeft)
 *         this.topRight = (topRight===undefined ? null : topRight)
 *         this.bottomLeft = (bottomLeft===undefined ? null : bottomLeft)
 *         this.bottomRight = (bottomRight===undefined ? null : bottomRight)
 *     }
 * }
 */

function construct(grid: number[][]): Node | null {
  const isCheck = (r0: number, r1: number, c0: number, c1: number): boolean => {
    for (let i = r0; i < r1; i++) {
      for (let j = c0; j < c1; j++) {
        if (grid[r0][c0] !== grid[i][j]) {
          return false;
        }
      }
    }
    return true;
  };
  const dfs = (r0: number, r1: number, c0: number, c1: number): Node | null => {
    const allSame = isCheck(r0, r1, c0, c1);

    // 所有网格值相同，表示是叶子节点
    if (allSame) {
      return new Node(grid[r0][c0] === 1, true);
    }

    const ans = new Node(
      false,
      false,
      dfs(r0, (r0 + r1) >> 1, c0, (c0 + c1) >> 1),
      dfs(r0, (r0 + r1) >> 1, (c0 + c1) >> 1, c1),
      dfs((r0 + r1) >> 1, r1, c0, (c0 + c1) >> 1),
      dfs((r0 + r1) >> 1, r1, (c0 + c1) >> 1, c1)
    );

    return ans;
  };

  const n = grid.length;
  return dfs(0, n, 0, n);
}
// @lc code=end
